#include <stdio.h>
#include <malloc.h>

//二叉搜索树 二叉排序树 binary search tree BST
typedef int ElementType;
typedef struct node *BST;
struct node{
    //1.数据项
    ElementType data;
    //2.两个指针
    struct node *left;
    struct node *right;
} ;

//插入
/*
 * 核心思想：待插入值value和当前结点的值做对比，
 * 如果value值较小，则该值需要插入到左子树。
 * 如果value值较大，则该值需要插入到右子树
 * */

/*
 * 函数名：insert createBST
 * 输入：根
 * 输出：根
 * */
BST insert(BST root,ElementType value){
    //1.树为空/或者当前结点不存在
    if(root==NULL){
        //1.分配空间
        root =malloc(sizeof(struct  node));
        //2.赋值
        root->data=value;
        root->left=NULL;
        root->right=NULL;
        return root;
    }
    if(value<root->data)
        root->left = insert(root->left,value);
    else if(value>root->data){
        root->right = insert(root->right,value);
    }
    return root;
}
//2.查找最大值
/*
 * 对于BST而言，包含最大键值的结点一定是树最右子结点。
 * 所以查找过程，就是指针不断往右走的过程。
 *
 * 函数名：findMax()
 * 输入：树（树的根）
 * 输出：返回包含该最大键值的结点
 * */
BST findMax(BST bst){
    //1.大前提 树为空肯定不存在
    if(bst ==NULL)
        return NULL;
    //2.在非空树里查找
    //定义一个指针，不断指向树的右子结点，来找到最右
    BST tmp =bst;
    while(tmp->right){
        tmp =tmp->right;
    }
    return tmp;
}

//查找最小值
/*
 * 函数名：fidmin
 * 输入：根结点
 * 输出：包含最小值的结点
 * */
BST findMin(BST bst){
    //树为空,单独处理
    if(bst==NULL){
        return NULL;
    }
    //树不为空
    BST tmp =bst;
    while(tmp->left!=NULL){
        tmp =tmp->left;
    }
    return tmp;
}





//根据特定值查找结点
/*
 * 值：value
 * 当前的结点 node
 *
 * value>node   往右
 * value<node   往左
 * value = node 找到
 * */
/*
 * 函数名：searchValue()
 * 输入：value,根结点
 * 输出：(1)结点   找到 返回结点  找不到 NULL
 *     （2）标志  找到 1 找不到 0
 * */
BST searchValue(ElementType value,BST root){
    //1.树为空
    if(root ==NULL)
        return NULL;
    //2.树不为空
    if(value >root->data){
       return searchValue(value,root->right);
    }
    if(value<root->data)
      return  searchValue(value,root->left);
    if(value == root->data)
        return root;
}

int main() {
    BST root =NULL;
    root = insert(root,5);
    root = insert(root,7);
    root = insert(root,8);
    root =  insert(root,6);

    root =  insert(root,10);
    //struct node * root;
    BST maxNode = findMax(root);
    printf("树的最大值是%d\n",maxNode->data);
    BST minNode = findMin(root);
    printf("树的最小值是%d\n",minNode->data);
    //printf("Hello, World!\n");
    int value =20;
    BST node = searchValue(value,root);
    if(node){
        printf("值为%d的节点存在\n",value);
    } else
        printf("值为%d的结点不存在\n",value);
    return 0;
}
